package advanced.sorting;

public class QuickSort {

    private int[] intlist;
    
    public QuickSort(int[] list)
    {
        this.intlist=list;
    }
    
    public void print()
    {
        for(int i=0; i<intlist.length; i++)
        {
                System.out.print(intlist[i]+" ");
        }
        System.out.println();
    }


    public int partition(int arr[], int left, int right)
    {  
        int l = left, r = right;  
        int tmp;  
        int pivot = arr[(left + right) / 2];  
        while (l <= r) 
        {        
            while (arr[l] < pivot)             
                    l++;
            while (arr[r] > pivot)
                    r--;
            if (l <= r) {  
                    tmp = arr[l];
                    arr[l] = arr[r];
                    arr[r] = tmp;
                    l++;
                    r--;
            }
        }
        return l;
    }

    public void quickSort(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
                quickSort(arr, left, index - 1);
        if (index < right)
                quickSort(arr, index, right);
    }

    public static void main(String args[])
    {
        int [] inta={33, 90, 2, 45, 1, 88, 75};
        QuickSort qs=new QuickSort(inta);
        qs.print();
        qs.quickSort(qs.intlist, 0,qs.intlist.length-1);
        qs.print();
    }

}
